﻿// 097. 约数之和.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>

using namespace std;

/*

https://www.acwing.com/problem/content/99/

假设现在有两个自然数 A 和 B，S 是 AB 的所有约数之和。

请你求出 Smod9901 的值是多少。

输入格式
在一行中输入用空格隔开的两个整数 A 和 B。

输出格式
输出一个整数，代表 Smod9901 的值。

数据范围
0≤A,B≤5×107
输入样例：
2 3
输出样例：
15
注意: A 和 B 不会同时为 0。
*/

int A, B;
const int MOD = 9901;
vector<pair<long long, long long>> vp;

void calc() {
    for (int i = 2; i * i <= A; i++) {
        int t = 0;
        while (A % i == 0) {
            A /= i; t++;
        }
        if(t!=0)
            vp.push_back({ i,t*B });
    }
    if (A != 1) { vp.push_back({ A,B }); }
}


/*
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
*/


long long qmi(long long v, long long mi,int MOD) {
    long long res = 1;
    while (mi) {
        if(mi&1){ res *= v; res %= MOD; }
        mi >>= 1;
        v *= v; v %= MOD;
    }

    return res;
}


long long sum(long long v, long long mi) {
    if (mi == 0) return 1;
    long long res = 0;
    if (mi % 2 == 0) {
        res = (qmi(v, mi,MOD) + (1 + qmi(v, mi / 2,MOD)) * sum(v, mi / 2-1))%MOD;
    }
    else {
        res = (qmi(v, mi, MOD) + sum(v, mi - 1))%MOD;
    }

    return res;
}

int main()
{
    cin >> A >> B;
    calc();
    long long ans  = 1;
    for (int i = 0; i < vp.size(); i++) {
        long long v = vp[i].first; long long mi = vp[i].second;
        ans *= sum(v, mi); ans %= MOD;
    }
    if (A == 0) ans = 0;
    cout << ans << endl;

  
    return 0;
}

 